﻿#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>

using namespace std;
//字符串
//二进制求和
class Solution {
public:
    string addBinary(string a, string b) {
        //模拟列竖式运算
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;
        while (cur1 >= 0 || cur2 >= 0 || t)
        {
            if (cur1 >= 0) t += a[cur1--] - '0';
            if (cur2 >= 0) t += b[cur2--] - '0';
            ret += t % 2 + '0';//实现从 尾部相加
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};




//二进制 相乘
class Solution {
public:
    string multiply(string n1, string n2) {
        //解法：无进位相乘后 相加，然后处理进位
        int m = n1.size(), n = n2.size();
        reverse(n1.begin(), n1.end());
        reverse(n2.begin(), n2.end());
        vector<int> tmp(m + n - 1);

        //1.无进位 相乘后相加
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');
            }

        int cur = 0, t = 0;
        string ret;
        while (cur < m + n - 1 || t)
        {
            if (cur < m + n - 1) t += tmp[cur++];
            ret += t % 10 + '0';
            t /= 10;
        }

        //处理 前导零
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();

        reverse(ret.begin(), ret.end());
        return ret;
    }
};



//删除字符中的所有相邻重复项
class Solution {
public:
    string removeDuplicates(string s) {
        //数组模拟 栈
        string ret;
        for (auto ch : s)
        {
            if (ret.size() && ch == ret.back())
                ret.pop_back();
            //有数字 且相等
            //出栈
            else ret += ch;
        }
        return ret;
    }
};


//⽐较含退格的字符串





//基本计算器ii
class Solution {
public:
    int calculate(string s) {
        vector<int> st;//用 数组 来模拟 栈结构
        int i = 0, n = s.size();
        char op = '+';
        while (i < n)
        {
            //分情况 来进行讨论

            //为空
            if (s[i] == ' ')
                i++;

            //是数字
            else if (s[i] >= '0' && s[i] <= '9')
            {
                //把数字 给提取 出来
                int tmp = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                //来提取出 所有的数字

                //判断 存储的 上一个字符
                if (op == '+')
                    st.push_back(tmp);
                else if (op == '-')
                    st.push_back(-tmp);
                else if (op == '*')
                    st.back() *= tmp;
                else st.back() /= tmp;
            }

            //是字符
            else
            {
                op = s[i];//直接刷新
                i++;
            }
        }

        int ret = 0;
        for (auto x : st)
            ret += x;
        return ret;
    }
};

//字符串 解码
class Solution {
public:
    string decodeString(string s)
    {
        stack<int> nums;
        stack<string> st;
        st.push("");//技巧 防越界
        int i = 0, n = s.size();

        while (i < n)
        {
            //逐个解析
            if (s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                //字符串类 数字 通用 读取方法
                while (s[i] >= '0' && s[i] <= '9')
                {
                    //识别到了 数字
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }
            else if (s[i] == '[')
            {
                i++;
                string tmp = "";//
                while (s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp);
                //入栈
            }

            else if (s[i] == ']')
            {
                string tmp = st.top();
                st.pop();
                int k = nums.top();
                nums.pop();
                //处理完 之后出栈

                //用完之后 就pop删去

                while (k--)
                {
                    st.top() += tmp;
                }
                i++;//跳过 这个右括号
            }
            else
            {
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.top() += tmp;//直接 放到 栈顶后
            }

        }
        return st.top();

    }
};

//验证 栈序列
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int i = 0, n = popped.size();
        for (auto x : pushed)
        {
            st.push(x);//一直进栈
            //判断 是否 出栈
            while (st.size() && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }
        return i == n;
    }
};

//队列+BFS
//N叉树的层序遍历
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;//记录最后的结果
        queue<Node*> q;
        if (root == nullptr) return ret;

        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for (Node* child : t->children)//让下一层 节点入队
                {
                    if (child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};




//二叉树的锯齿形 层序遍历
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;
        queue<TreeNode*> q;
        q.push(root);//用队列 来实现 模拟
        int level = 1;
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                auto t = q.front();
                q.pop();
                tmp.push_back(t->val);

                //使树的左右 节点入队
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            //判断 是否逆序
            if (level % 2 == 0) reverse(tmp.begin(), tmp.end());
            ret.push_back(tmp);
            level++;
        }
        return ret;
    }
};


//⼆叉树的最⼤宽度
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*, unsigned int>> q;//用 数组模拟队列
        q.push_back({ root,1 });
        unsigned int ret = 0;

        while (q.size())
        {
            //先更新 这一层的 宽度
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);

            //让 下一层 进队
            vector<pair<TreeNode*, unsigned int>> tmp;
            //让 下一层 入队
            for (auto& [x, y] : q)
            {
                if (x->left) tmp.push_back({ x->left,y * 2 });
                if (x->right) tmp.push_back({ x->right,y * 2 + 1 });
            }
            q = tmp;//更新队列
            //和之前的对比
            // 数组 模拟的队列
        }
        return ret;
    }
};